package chapter_03;


public class SelectSort extends BubbleSort{
    // 选择排序
    /*
    简述：
    选择排序是把所有的元素扫一遍，从中挑出（或者选择，这正是这个排序名字的由来）最小的
    一个元素。最小的元素和这个序列最左端的元素交换位置，即和索引为0的数据项交换位置。现
    在最左端的元素是有序的了，不需要再交换位置了。
    再次扫描序列时，就从索引为1的位置开始，还是寻找最小的，然后和索引为1的数据项交换，
    这个过程一直持续到所有的元素都排定。

    不变性：选择排序中，下标小于或等于out的位置的数据项总是有序的
    选择排序的效率：选择排序和冒泡排序执行了相同次数的比较：N*(N-1)/2。对于10个数据项，
    需要45次比较。然而，10个数据项只需要少于10次交换。对于100个数据项，需要4950次比较，
    但只进行了不到100次的交换。N值很大时，比较的次数是主要的，所以结论是选择排序和冒泡
    排序一样运行了O(N^2)时间。但是，选择排序无疑更快，因为它进行的交换少得多。当N值较小
    时，特别是如果交换的时间级比比较的时间级大得多时，选择排序实际上是相当快的。
     */

    SelectSort(int max) {
        super(max);
    }

    public void sort() {
        int out, in, min;
        for (out = 0; out < nElems - 1; out++) {
            min = out;  // 默认外层循环的第一个元素是最小的
            for (in = out + 1; in < nElems; in++)
                if (a[in] < a[min])
                    min = in;
            swap(out, min);
        }
    }

    public static void main(String[] args) {
        int maxSize = 10;
        BubbleSort arr;
        arr = new SelectSort(maxSize);

        arr.insert(77);
        arr.insert(99);
        arr.insert(44);
        arr.insert(55);
        arr.insert(22);
        arr.insert(88);
        arr.insert(11);
        arr.insert(00);
        arr.insert(66);
        arr.insert(33);
        arr.display();
        arr.sort();
        arr.display();
    }
}
